package 力扣.动态规划;

public class 区域和检索_数组不可变303 {
    private int[] sums;
    // * 朴素的解法：直接累加和。
    //   缺点：每次调用 {sumRange}sumRange 时，通过循环的方法计算数组nums 从下标 i 到下标 j 范围内的元素和，需要计算 j−i+1 个元素的和。
    //   由于每次检索的时间和检索的下标范围有关，因此检索的时间复杂度较高，如果检索次数较多，则会超出时间限制

/*    public 区域和检索_数组不可变303(int[] nums) {
          this.sums = nums;
    }

    public int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j ; k++) {
            sum += nums[k];
        }
        return sum;
    }*/

    //进阶版：前缀和
    public 区域和检索_数组不可变303(int[] nums){
        sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = sums[i] +nums[i];
        }
    }
    public int sumRange(int i , int j){
          return sums[j + 1] - sums[i] ;//只执行一次
    }

    public static void main(String[] args) {
        int[] ints = {-2, 0, 3, -5, 2, -1};
        区域和检索_数组不可变303 t1 = new 区域和检索_数组不可变303(ints);
        int i = t1.sumRange(0, 2);
        System.out.println(i);
    }

}
